package cn.zifangsky.dp.questions;

import org.junit.Test;

/**
 * 斐波那契数列问题
 * <p>f(n) = f(n-1) + f(n-2)</p>
 *
 * @author zifangsky
 * @date 2020/5/25
 * @since 1.0.0
 */
public class Problem_002_FibonacciSequence {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int n = 6;

        //1. 测试方法一
        System.out.println(solution1(n));
        //2. 测试方法二
        System.out.println(solution2(n));
    }


    /**
     * 解法一：根据公式<b> f(n) = f(n-1) + f(n-2) </b>，使用暴力递归方式求解
     *
     * @param n 第 N 项
     */
    private int solution1(int n){
        if(n < 1){
            return 0;
        }

        if(n == 1 || n == 2){
            return 1;
        }

        return solution1(n - 1) + solution1(n - 2);
    }

    /**
     * 解法二：根据公式<b> f(n) = f(n-1) + f(n-2) </b>，从左到右把数列的每一项值都求解出来
     *
     * @param n 第 N 项
     */
    private int solution2(int n){
        if(n < 1){
            return 0;
        }

        if(n == 1 || n == 2){
            return 1;
        }

        //默认为第2项
        int result = 1;
        //默认为第1项
        int pre = 1;
        int tmp = 0;

        for(int i = 3; i <= n; i++){
            tmp = result;
            result = result + pre;
            pre = tmp;
        }

        return result;
    }


}
